using System;
using System.Collections.Generic;
using System.Text;

namespace XnaDevRu.Bullet
{
	public class UnionFind : IDisposable
	{
		private List<Element> _elements = new List<Element>();

		public int ElementCount
		{
			get { return _elements.Count; }
		}

		public void SortIslands()
		{
			for (int i = 0; i < ElementCount; i++)
			{
				Element element = _elements[i];
				element.Id = Find(i);
				element.Size = i;
			}

			_elements.Sort(Sort);
		}

		private static int Sort(Element x, Element y)
		{
			if (x.Id < y.Id) return -1;
			else if (x.Id > y.Id) return 1;
			else return 0;
		}

		public void Reset(int number)
		{
			Allocate(number);

			for (int i = 0; i < number; i++)
			{
				Element element = new Element();
				element.Id = i; element.Size = 1;
				//elements[i] = element;
				_elements.Insert(i, element);
			}
		}

		public bool IsRoot(int index)
		{
			return (_elements[index].Size == index);
		}

		public Element this[int index]
		{
			get { return _elements[index]; }
		}

		public void Allocate(int number)
		{
			//Does nothing
			_elements = new List<Element>(number);
		}

		public bool Find(int i, int j)
		{
			return (Find(i) == Find(j));
		}

		public int Find(int i)
		{
			while (i != _elements[i].Id)
			{
				Element element = _elements[i];
				element.Id = _elements[_elements[i].Id].Id;
				_elements[i] = element;
				i = _elements[i].Id;
			}

			return i;
		}

		public void Unite(int p, int q)
		{
			int i = Find(p), j = Find(q);
			if (i == j)
				return;

			//weighted quick union, this keeps the 'trees' balanced, and keeps performance of unite O( log(n) )
			if (_elements[i].Size < _elements[j].Size)
			{
				Element element = _elements[i];
				element.Id = j;
				_elements[i] = element;

				element = _elements[j];
				element.Size += _elements[i].Size;
				_elements[j] = element;
			}
			else
			{
				Element element = _elements[j];
				element.Id = i;
				_elements[j] = element;

				element = _elements[i];
				element.Size += _elements[j].Size;
				_elements[i] = element;
			}
		}

		#region IDisposable Members

		public void Dispose()
		{
			_elements.Clear();
		}

		#endregion
	}

	public class Element
	{
		private int _id;
		private int _size;

		public int Id { get { return _id; } set { _id = value; } }
		public int Size { get { return _size; } set { _size = value; } }
	}
}